package myutil.concurrency;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.CompletionService;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Hlib_Babii
 */
public class ParalelMergeSort {

    static class MergeSortTask implements Callable<int[]> {

        private final int[] toSort;

        public MergeSortTask(int[] toSort) {
            this.toSort = toSort;
        }

        @Override
        public int[] call() throws Exception {
            return ParalelMergeSort.sort(toSort);
        }
    }

    /**
     * Merges two arrays into one
     *
     * @return merged array
     * @throws Exception
     */
    private static int[] merge(int[] first, int[] second) {
        int[] result = new int[first.length + second.length];
        int index1 = 0;
        int index2 = 0;

        while (index1 < first.length && index2 < second.length) {
            if (first[index1] <= second[index2]) {
                result[index1 + index2] = first[index1];
                ++index1;
            } else {
                result[index1 + index2] = second[index2];
                ++index2;
            }
        }

        if (index1 < first.length) {
            System.arraycopy(first, index1, result, index1 + index2, first.length - index1);
        } else if (index2 < second.length) {
            System.arraycopy(second, index2, result, index1 + index2, second.length - index2);
        }

        return result;
    }

    public static int[] sort(int[] array) {
        if (array.length <= 1) {
            return array;
        }

        int leftLength = array.length / 2;
        int[] left = Arrays.copyOf(array, leftLength);
        int[] right = Arrays.copyOfRange(array, leftLength, array.length);
        
        int[] sortedLeft = sort(left);
        
        ExecutorService executorService = Executors.newCachedThreadPool();
        Future<int[]> sortedFuture;
        sortedFuture = executorService.submit(new MergeSortTask(right));
        int[] sortedRight = null;
        try {
            sortedRight = sortedFuture.get();
        } catch (InterruptedException | ExecutionException ex) {
            // not going to be thrown
        }

        return merge(sortedLeft, sortedRight);
    }

    public static void main(String[] args) {
        int[] a = new int[1500];
        final Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(1000);
        }
        System.out.println(Arrays.toString(a));
        long start = System.currentTimeMillis();
        System.out.println(Arrays.toString(sort(a)));
        //Arrays.sort(a);
        //System.out.println(Arrays.toString(a));
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
}
